BSGS
int qpow(int a,int b,int p)
{
int res = 1 % p;
while(b)
{
if(b & 1) res = (1ll * res * a) % p;
a = (1ll * a * a) % p;
b >>= 1;
}
return res;
}
int BSGS(int a,int b,int p)
{
map<int,int> tbl;
int t = sqrt(p) + 1;
for(int j = 0;j < t;++j)
{
int val = (1ll * b * qpow(a,j,p)) % p;
tbl[val] = j;
}
a = qpow(a,t,p);
if(a == 0) return b == 0 ? 0 : -1;
for(int i = 0;i <= t;++i)
{
int val = qpow(a,i,p);
int j = tbl.find(val) == tbl.end() ? -1 : tbl[val];
if(j >= 0 && i * t - j >= 0) return i * t - j;
}
return -1;
}
exgcd
int exgcd(int a,int b,int& x,int& y)
{
if(b == 0)
{
x = 1,y = 0;
return a;
}
int d = exgcd(b,a%b,y,x);
y -= a/b*x;
return d;
}